Aaron Sidford
In this talk I will present a new cutting plane method as well as techniques for applying this method to achieve faster asymptotic running times for fundamental problems in both combinatorial and continuous optimization. After providing an overview of cutting plane methods and our improvement, I will discuss how they can be used to improve the running time for solving problems ranging from matroid intersection to semidefinite programming to submodular flow. Furthermore, I will show how our techniques can be used to improve both the weakly polynomial and strongly polynomial running times for submodular function minimization. No previous experience with cutting plane methods or submodular functions required.
This talk is based on joint work with Yin Tat Lee and Sam Wong and is based primarily on A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.